package main

import "fmt"

type IpNode struct {
	Ip  string
	Num int
}

//实现最小堆
type Heap struct {
	n      int
	data   []IpNode
	length int
}

func (t *Heap) Pop() (ret IpNode) {
	if t.length <= 0 {
		panic("no data")
	}
	ret = t.data[0]
	t.data[0] = t.data[t.length-1]
	t.length -= 1
	i := 0
	for i < t.length {
		l := ((i + 1) << 1) - 1
		r := ((i+1)<<1 | 1) - 1
		//fmt.Print(i, l, r)
		next := l
		if r < t.length && l < t.length {
			if t.data[l].Num > t.data[r].Num {
				next = r
			}
		} else if l < t.length {
			next = l
		} else {
			break
		}
		if t.data[next].Num < t.data[i].Num {
			t.data[next], t.data[i] = t.data[i], t.data[next]
			i = next
		} else {
			break
		}
	}
	return
}

func (t *Heap) push(x IpNode) {
	if t.length >= len(t.data) {
		return
	}
	t.length += 1
	i := t.length - 1
	t.data[i] = x
	for {
		p := ((i + 1) >> 1) - 1
		if p < 0 {
			break
		}
		if t.data[i].Num < t.data[p].Num {
			t.data[i], t.data[p] = t.data[p], t.data[i]
		}
		i = p
	}
}

func (t *Heap) Push(x IpNode) {
	if x.Num <= t.data[0].Num && t.length >= len(t.data) {
		return
	}
	if t.length >= len(t.data) {
		t.Pop()
	}
	t.push(x)
}

func (t *Heap) Print() {
	for t.length > 0 {
		fmt.Printf("%v,", t.Pop())
	}
}

func NewHeap(n int) (ret Heap) {
	return Heap{
		n:      n,
		data:   make([]IpNode, n),
		length: 0,
	}
}
